# -*- coding: utf-8 -*-

from sort import quick

def simple_find(item, sorted_arr):
    """附加条件：有序顺序表中元素不重复，找到等于item的元素"""
    def erfen(imin, imax):
        if imax-imin == 1:
            if sorted_arr[imin] == item:
                return imin
            elif sorted_arr[imax] == item:
                return imax
            else:
                return None
        
        imiddle = (imin+imax)//2
        middle = sorted_arr[imiddle]
        if item > middle:
            return erfen(imiddle, imax)
        elif item < middle:
            return erfen(imin, imiddle)
        elif item == middle:
            return imiddle
    
    return erfen(0, len(sorted_arr)-1)

def find_first(item, sorted_arr):
    """找到等于item的第一个元素：
    1）找到任意一个等于item的元素
    2）在最后的区间[imin, icurr]中二分查找第一个等于item的元素"""
    def erfen(imin, imax):
        if imax-imin == 1:
            if sorted_arr[imin] == item:
                return (imin, imin)
            elif sorted_arr[imax] == item:
                return (imin, imax)
            else:
                return None
        
        imiddle = (imin+imax)//2
        middle = sorted_arr[imiddle]
        if item > middle:
            return erfen(imiddle, imax)
        elif item < middle:
            return erfen(imin, imiddle)
        elif item == middle:
            return (imin, imiddle)

    def erfenx(imin, imax):
        if imax - imin == 1:
            return imax
        imiddle = (imin+imax)//2
        middle = sorted_arr[imiddle]
        if item == middle:
            return erfenx(imin, imiddle)
        else:
            return erfenx(imiddle, imax)

    rs = erfen(0, len(sorted_arr)-1)
    if not rs:
        return None
    
    imin, icurr = rs[0], rs[1]
    if not imin:
        return imin
    elif sorted_arr[icurr-1] != item:
        return icurr
    else:
        return erfenx(imin, icurr)


def find_last(item, sorted_arr):
    """找到等于item最后一个元素：
    同找到第一个元素"""
    def erfen(imin, imax):
        if imax-imin == 1:
            if sorted_arr[imin] == item:
                return (imin, imax)
            elif sorted_arr[imax] == item:
                return (imax, imax)
            else:
                return None
        
        imiddle = (imin+imax)//2
        middle = sorted_arr[imiddle]
        if item > middle:
            return erfen(imiddle, imax)
        elif item < middle:
            return erfen(imin, imiddle)
        elif item == middle:
            return (imiddle, imax)

    def erfenx(imin, imax):
        if imax - imin == 1:
            return imin
        imiddle = (imin+imax)//2
        middle = sorted_arr[imiddle]
        if item == middle:
            return erfenx(imiddle, imax)
        else:
            return erfenx(imin, imiddle)

    rs = erfen(0, len(sorted_arr)-1)
    if not rs:
        return None
    
    icurr, imax = rs[0], rs[1]
    if imax == icurr:
        return imax
    elif sorted_arr[icurr+1] != item:
        return icurr
    else:
        return erfenx(icurr, imax)

def find_floor(item, sorted_arr):
    """以item为下限，找到第一个大于或等于item的元素"""
    def erfen(imin, imax):
        if imax-imin == 1:
            if item > sorted_arr[imax]:
                return None
            elif item <= sorted_arr[imin]:
                return imin
            else:
                return imax
        imiddle = (imin+imax)//2
        middle = sorted_arr[imiddle]
        if middle < item:
            return erfen(imiddle, imax)
        else:
            return erfen(imin, imiddle)
    return erfen(0, len(sorted_arr)-1)

def find_upper(item, sorted_arr):
    """以item为上限，找到最后一个小于或等于item的元素"""
    def erfen(imin, imax):
        if imax-imin == 1:
            if item < sorted_arr[imin]:
                return None
            elif item >= sorted_arr[imax]:
                return imax
            else:
                return imin
        imiddle = (imin+imax)//2
        middle = sorted_arr[imiddle]
        if middle > item:
            return erfen(imin, imiddle)
        else:
            return erfen(imiddle, imax)
    return erfen(0, len(sorted_arr)-1)


if __name__ == '__main__':
    li = [0,1,2,3,4,5,6,7,8,9]
    sl = quick(li)
    print(sl)
    print(simple_find(9, sl))

    li = [0,3,9,5,6,7,10,58,694,58,26,10,3,-8,58,799,58,21,11,23,59,73,168,258]
    sl = quick(li)
    
    print(list(range(0, len(sl))))
    print(sl)
    print(find_first(58, sl))
    print(find_last(58, sl))
    print(find_floor(58, sl))
    print(find_upper(58, sl))
